Subject: Re: QoS R - best route versus good enough route....

From: [email-masked] (Ariel Orda)
Date: Tue, 29 Apr 1997 17:41:48 +0300

The purpose of this note is to expand on some recent discussions
conducted on the mailing list and triggered by several
proposals ([MaSt] and [CCS], see below for exact references) 
aimed at taking advantage of the properties of some schedulers 
when computing paths that satisfy end-to-end delay bounds.
We would like to clarify some of the aspects and assumptions of the
above two proposals, and also point that many of the underlying
issues can actually be looked at in a somewhat broader setting as
was previously articulated in [GuOr] (of which [GO2] is a recent
conference publication) and [GOW] (see again below for exact
references).

The basic premise of both [CCS] and [MaSt] is that the complexity 
of computing paths that provide end-to-end delay guarantees can 
be reduced when certain types of schedulers are used in the network.
In particular, rate-based schedulers such as those assumed in the
specification of the end-to-end delay bounds of the Guaranteed
Service [GS96], allow the mapping of delay guarantees into rate
guarantees. This fact can then be exploited to reduce the complexity
of the path selection algorithm. In [CCS], this is done by assuming
that the bandwidth is known a-priori, i.e., is INDEPENDENT of the 
delay bound and the selected path. Under this assumption, it is 
shown how the required path can be identified by a standard shortest 
path algorithm. In [MaSt], such an assumption is not made, thus a 
shortest path algorithm is executed for each possible bandwidth (rate) 
value (up to M executions, where M is the number of network links).
As pointed out in [CCS] and [MaSt], such simplifications are also 
applicable to other constraints such as end-to-end jitter and 
losslessness, which can be similarly incorporated in the path selection 
algorithm.  

The problem considered in [GuOr] is a similar one, but cast in a more 
general (and much harder) setting. The generalization is in allowing 
some level of uncertainty in the bandwidth available on each link, i.e., 
a probabilistic setting. In addition to establishing a number of 
intractability results (sic), "optimal" algorithms are also identified for 
a number of special cases. In particular, it was shown that for the 
deterministic case considered in [MaSt] and [CCS], a solution can be 
obtained through up to M executions of a standard shortest path algorithm, 
i.e., as subsequently pointed out in [MaSt]. A specific implementation 
is provided in [GOW], that is based on the Bellman-Ford algorithm. Here, 
it is important to note, as was pointed out by Qingming in a recent mail, 
that the assumption made in [CCS] on an a-priori fixed bandwidth value 
(independent of the path and the delay requirement), while it provides a 
simpler solution, is quite limiting. In particular, it does not capture 
the ability of the rate based model of [GS96] to adjust the end-to-end 
delay through the requested service rate.

Finally, it should be pointed out that the method employed in all of the 
above studies (for the deterministic case), relies on an observation which, 
while interesting, is quite straightforward. As is acknowledged in [GuOr],
the simple technique of running a shortest path algorithm for each 
bandwidth value has been employed in a previous study, although not 
in the context of WFQ schedulers ([GuOr], ref. [13]).  

In our view, this simple solution is still unsatisfactory and calls
for additional work. One important issue is how to cope with
imprecision of dynamic parameters, in particular link residual rates.
This is what motivated our study [GuOr], and we are currently working 
on some extensions. Another important issue is that of complexity: 
for example, executing the Bellman-Ford algorithm M times
incurs a complexity of O(N*M^2), which may well be prohibitive. This
issue, as well as the establishment of multiple connections and load
balancing, are addressed in [Ord]. 

As was mentioned earlier, the incorporation of QoS constraints
other than delay is clearly of interest, and some interesting results
appear in [CCS] and [MaSt], which observe that the basic algorithm for
end-to-end delays can accommodate additional constraints, such as jitter.

Roch Guerin and Ariel Orda

References

[CCS] Chotipat Pornavalai, Goutam Chakraborty and Norio Shiratori,
      "QoS Based Routing Algorithm in Integrated Services Packet
      Networks", January 1997.

[GuOr] Roch Guerin and Ariel Orda, "QoS-based routing in Networks with
       Inaccurate Information: Theory and Algorithms". IBM Report,
       July 96. (Available through http://www.watson.ibm.com:8080/.)

[GO2] Roch Guerin and Ariel Orda, "QoS-based routing in Networks with
       Inaccurate Information: Theory and Algorithms". In Proceedings
       of Infocom'97.

[GOW] Roch Guerin, Ariel Orda and Doug Williams, "QoS routing Mechanisms
      and OSPF Extensions", Internet Draft, December 96.
      (draft-guerin-qos-routing-ospf-00.txt).

[GS96] S. Shenker, C. Partridge, and R. Guerin, "Specification of 
       Guaranteed Quality of Service." Internet Draft, Int-Serv Working
       Group, February 1997, (draft-ietf-intserv-guaranteed-svc-07.txt).

[MaSt] Qingming Ma and Peter Steenkiste, "Quality of Service Routing
       for Traffic with Performance Guarantees", 1997.

[Ord] Ariel Orda, "Routing with End to End QoS Guarantees in
      Broadband Networks". Technical Report, EE Dept., Technion, Haifa,
      Israel (to appear).

---

From: Masataka Ohta <[email-masked]>
Date: Wed, 30 Apr 97 19:02:24 JST

Ariel;

> be reduced when certain types of schedulers are used in the network.

The assumption is too strong that the algorithm is unusable
after hierarchical aggregation when a single aggregated link
actually consists of cascaded WFQ relays.

For example, the algorithm does not work if an ATM network is
abstracted as a single link. But, don't bother to develop an
integrated IP-ATM P.NNI, becasue the algorithm does not work
with P.NNI aggregation, either.

> Here, 

Qingming made a mistake to think that a shortest path at certain rate
is still the shortest path at a different rate and metric.

							Masataka Ohta